package com.practice.tree;

import com.practice.util.BinaryTree;
import com.practice.util.BinaryTreeNode;

public class FindMaxSumPath {
	public String maxPath(BinaryTree tree) {
		return maxPath(tree.getRoot()).path;
	}
	
	private Path maxPath(BinaryTreeNode node) {
		if (node == null) return new Path("", 0);
		Path left = maxPath(node.left());
		Path right = maxPath(node.right());
		if (left.value >= right.value) {
			return new Path(node.value() + " " + left.path, node.value() + left.value); 
		}
		else {
			return new Path(node.value() + " " + right.path, node.value() + right.value);
		}
	}
	
	private class Path {
		String 	path;
		int		value;
		
		public Path(String path, int value) {
			this.path = path;
			this.value = value;
		}
	}
}
